(a). Field of the Invention
The present invention relates to data decoding, and more particularly, to Viterbi decoding.
(b). Description of the Related Arts
Viterbi decoding is a common technique for decoding received convolutional-coded data. FIG. 1 is a diagram showing the architecture of a conventional Viterbi decoder. In FIG. 1, encoded data is provided to a branch metric unit 11 for computing all branch metrics for each node (or state) in a trellis diagram. Next, an add-compare-select (ACS) unit 12 accumulates the associated branch metric to each path metric, compares the path metrics of all the paths entering the same node, selects the path with the lowest path metric (i.e. the surviving path), and outputs a corresponding decision bit. Meanwhile, the ACS unit 12 stores each accumulated path metric back to a path metric memory unit 13. Lastly, a survivor memory management unit 14 determines a surviving path with maximum likelihood according to the decision bits outputted by the ACS unit 12, and outputs corresponding decoded data.
There are two approaches widely known in the art to implement the survivor memory management unit 14: register exchange approach and traceback approach. The register exchange approach directly stores the decoded data corresponding to each surviving path according to the decision bits; while the traceback approach records the path history of each surviving path used for performing tracing back, so as to generate the decoded data.
In the traceback approach, a two-dimensional memory is used to store the path history. The two-dimensional memory includes N rows (N being the number of the trellis-states), and the N decision bits generated during each symbol interval are stored into one column of the memory. According to the periodical article by G. Feygin and P. Gulak, “Architectural tradeoffs for survivor sequence memory management in Viterbi decoders”, IEEE Transactions on Communications, vol. 41, issue 3, pp. 425-429, March 1993, three types of operations are performed in a traceback Viterbi decoder: Traceback Read, Decode Read, and Writing New Data. The three operations are performed simultaneously to read from and write into the two-dimensional memory. Said article suggests four algorithms for the traceback approach: k-pointer even algorithm, k-pointer odd algorithm, one-pointer algorithm, and hybrid algorithm. In k-pointer even algorithm, the required number of memory columns is 2 kT/(k−1), where T represents the number of memory columns required to perform Traceback Read before Decode Read is performed. In k-pointer odd algorithm, the required number of memory columns is T(2 k−1)/(k−1). One-pointer algorithm is used to save memory space. However, since one-pointer algorithm uses a single read pointer and a single write pointer, the operating rate of Traceback Read or Decode Read is required to be k times of that of Writing New Data. That is, if Writing New Data operates in the rate of f MHz, then Traceback/Decode Read needs to operate in the rate of k×f MHz. This would cause design complexity and difficulty for a high data rate system. In addition, though hybrid algorithm combines the concepts of k-pointer (even or odd) algorithm and one-pointer algorithm, the restriction mentioned above still exists: in order to save memory space, the operating rate of Traceback/Decode Read increases.